/*
 * topological-hex, a program to compute combinatorial hexahedral meshes.
 *
 * Copyright (C) <2018> <Université catholique de Louvain (UCL), Belgique>
 *
 * List of the contributors to the development, description and complete
 * License: see LICENSE file.
 *
 * This program (topological-hex) is free software:
 * you can redistribute it and/or modify it under the terms
 * of the GNU General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program (see COPYING file).  If not,
 * see <http://www.gnu.org/licenses/>.
 */


#include <check.h>
#include <stdlib.h>

#include "sparse_set.h"

void check_consistency(const sparse_set *set) {
  ck_assert_msg(set->size <= set->capacity);

  for (uint32_t i = 0; i < set->capacity; i++) {
    ck_assert_msg(set->indices[i] < set->capacity,
                  "Value %u has out-of-bounds index %u",
                  i, set->indices[i]);
    ck_assert_msg(set->data[set->indices[i]] == i,
                  "Index for value %u contains incorrect value %u",
                  i, set->data[set->indices[i]]);
  }
}

static
void check_contents(const sparse_set *set,
                    uint32_t *values, uint32_t n) {
  ck_assert_msg(set->size == n,
                "Set contains %u elements, was expected to contain %u",
                set->size, n);

  for (uint32_t i = 0; i < n; i++) {
    ck_assert_msg(set->indices[values[i]] < n,
                  "Set should countain %u, but its index is %u which is "
                  "out-of-bounds", values[i], set->indices[values[i]]);
  }
}

START_TEST(test_init_empty) {
  uint32_t sizes[] = {0, 1, 4, 225, 512, 893};

  for (uint32_t i = 0; i < sizeof(sizes)/sizeof(*sizes); i++) {
    sparse_set set;
    ck_assert(sparse_set_init(&set, sizes[i]) == SUCCESS);
    check_consistency(&set);
    ck_assert(set.size == 0);
    sparse_set_release(&set);
  }
} END_TEST

START_TEST(test_insert_remove) {
  sparse_set set;
  ck_assert(sparse_set_init(&set, 128) == SUCCESS);

  sparse_set_insert(&set, 3);
  sparse_set_insert(&set, 127);
  sparse_set_insert(&set, 64);
  sparse_set_insert(&set, 52);
  sparse_set_insert(&set, 64);
  sparse_set_insert(&set, 127);
  sparse_set_insert(&set, 63);
  sparse_set_insert(&set, 0);

  {
    uint32_t contents[] = {0, 3, 52, 63, 64, 127};
    check_contents(&set, contents, sizeof(contents)/sizeof(*contents));
  }

  sparse_set_remove(&set, 63);
  sparse_set_remove(&set, 0);
  sparse_set_remove(&set, 0);
  sparse_set_remove(&set, 99);
  sparse_set_remove(&set, 99);
  sparse_set_remove(&set, 52);

  {
    uint32_t contents[] = {3, 64, 127};
    check_contents(&set, contents, sizeof(contents)/sizeof(*contents));
  }

  sparse_set_insert(&set, 3);
  sparse_set_remove(&set, 3);

  sparse_set_insert(&set, 93);
  sparse_set_insert(&set, 126);
  sparse_set_remove(&set, 64);
  sparse_set_remove(&set, 64);
  sparse_set_insert(&set, 72);
  sparse_set_insert(&set, 89);
  sparse_set_insert(&set, 72);
  sparse_set_insert(&set, 127);

  {
    uint32_t contents[] = {72, 89, 93, 126, 127};
    check_contents(&set, contents, sizeof(contents)/sizeof(*contents));
  }

  sparse_set_release(&set);
} END_TEST

Suite *sparse_set_suite(void) {
  Suite *s = suite_create("Sparse Set");

  TCase *tcase = tcase_create("Sparse Set");
  tcase_add_test(tcase, test_init_empty);
  tcase_add_test(tcase, test_insert_remove);
  suite_add_tcase(s, tcase);

  return s;
}
